#include "cache.h"
#include <slice.h>
#include <mutexlock.h>
#include <port_stdcxx.h>

namespace minidb
{

struct LRUHandle
{
    char key_data_[1]; // 柔性数组充当键,key_length_表示该键长度
    std::size_t key_length_;
    void *value_;                                // value_ 值
    void (*deleter)(const Slice &, void *value); // 删除器，用于析构value_
    LRUHandle *prev_, *next_;                    // lru节点
    std::size_t hash_;                           // hash值
    LRUHandle *next_hash_;                       // hash节点
    std::size_t charge_;                         // 负载
    std::size_t refs_;                           // 引用计数
    bool in_cache_;                              // 是否在cache中

    Slice key() const
    {
        // 只有在list头节点时，next_ == this。list头节点的key无意义
        assert(next_ != this);
        return Slice(key_data_, key_length_);
    }
};

/**
 * HashTable示意图
 * list_-----
 *           |          prev_/next_
 *        LRUHandle* <--------------->LRUHandle*
 *           |                             |
 *          next_hash_                  next_hash_
 *
 */
class HashTable
{
public:
    LRUHandle *Remove(const Slice &key, std::size_t hash)
    {
        LRUHandle **ptr = FindPointer(key, hash);
        LRUHandle *result = *ptr;
        if (result != nullptr)
        {
            --elems_;
            *ptr = result->next_hash_;
        }
        return result;
    }

    LRUHandle *Lookup(const Slice &key, std::size_t hash)
    {
        return *FindPointer(key, hash);
    }

    /// @brief 插入新节点,返回旧节点或nullptr
    /// @param h 新节点
    /// @return 旧节点或nullptr
    LRUHandle *Insert(LRUHandle *h)
    {
        if (!h) return nullptr;
        // note: 拿到指向目标指针的上一级指针,拿到上一级指针的好处是可以直接修改指针的指向,而不用通过链表的上一个节点进行修改
        LRUHandle **ptr = FindPointer(h->key(), h->hash_);
        LRUHandle *old = *ptr;
        h->next_hash_ = (old == nullptr ? nullptr : old->next_hash_);
        *ptr = h; // 不用通过prev,而是原地修改指针指向的节点,修改指针,指向新的节点
        if (old == nullptr)
        {
            ++elems_;
            if (elems_ > length_)
            {
                Resize();
            }
        }
        return old; // 返回旧节点
    }

private:
    LRUHandle **list_;   // lru & 双链表
    std::size_t length_; // 双链表长度
    std::size_t elems_;  // 元素数量

    LRUHandle **FindPointer(const Slice &key, std::size_t hash)
    {
        LRUHandle **ptr = &(list_[hash & (length_ - 1)]);
        while ((*ptr) != nullptr && ((*ptr)->hash_ != hash || (*ptr)->key() != key))
        {
            ptr = &(*ptr)->next_hash_;
        }
        return ptr;
    }

    void Resize()
    {
        std::size_t new_length = 4;
        while (new_length < elems_)
        {
            new_length *= 2;
        }
        LRUHandle **new_list = new LRUHandle *[new_length];

        memset(new_list, 0, sizeof(LRUHandle *) * new_length);
        int count = 0;
        for (std::size_t i = 0; i < length_; i++)
        {
            LRUHandle *h = list_[i];
            while (h != nullptr)
            {
                LRUHandle **ptr = &new_list[h->hash_ & (new_length - 1)];
                LRUHandle *next = h->next_hash_;
                h->next_hash_ = *ptr;
                *ptr = h;
                h = next;
                ++count;
            }
        }
        assert(elems_ == count);
        delete[] list_;
        length_ = new_length;
        list_ = new_list;
    }
};

class LRUCache
{
public:
    LRUCache();

    ~LRUCache();

    void SetCapacity(std::size_t capacity)
    {
        capacity_ = capacity;
    }

    // Like Cache methods, but with an extra "hash" parameter.
    Cache::Handle *Insert(const Slice &key, uint32_t hash, void *value,
                          size_t charge,
                          void (*deleter)(const Slice &key, void *value));

    Cache::Handle *Lookup(const Slice &key, uint32_t hash);

    void Release(Cache::Handle *handle);

    void Erase(const Slice &key, uint32_t hash);

    void Prune();

    std::size_t TotalCharge() const
    {
        MutexLock lock(&mutex_);
        return usage_;
    }

private:
    void LRU_Append(LRUHandle *list, LRUHandle *e);

    void LRU_Remove(LRUHandle *e);

    bool FinishErase(LRUHandle *e);

    void Ref(LRUHandle *e);

    void Unref(LRUHandle *e);

private:
    mutable port::Mutex mutex_;
    std::size_t capacity_; // 容量
    std::size_t usage_;    // 已使用空间
    HashTable table_;      // hash表
    LRUHandle lru_;        // lru链表，refs==1，未被用户使用的节点，插入节点时如果空间不足淘汰lru_的节点
    LRUHandle in_used_;    // in_used_链表，refs>=2 && in_cache_=true，用户正在使用的节点
};

LRUCache::LRUCache() :
    capacity_(0),
    usage_(0)
{
    lru_.next_ = &lru_;
    lru_.prev_ = &lru_;
    in_used_.next_ = &in_used_;
    in_used_.prev_ = &in_used_;
}

LRUCache::~LRUCache()
{
    assert(in_used_.next_ == &in_used_);
    for (LRUHandle *e = &lru_; e->next_ != &lru_;)
    {
        LRUHandle *next = e->next_;
        assert(e->in_cache_);
        e->in_cache_ = false;
        assert(e->refs_ == 1);
        Unref(e);
        e = next;
    }
}

void LRUCache::LRU_Append(LRUHandle *list, LRUHandle *e)
{
    // note: lru_、in_used_都是环形链表，所以Append、Remove操作都可以不用判空
    e->next_ = list;
    e->prev_ = list->prev_;
    e->prev_->next_ = e;
    e->next_->prev_ = e;
}

void LRUCache::LRU_Remove(LRUHandle *e)
{
    // note: lru_、in_used_都是环形链表，所以Append、Remove操作都可以不用判空
    e->next_->prev_ = e->prev_;
    e->prev_->next_ = e->next_;
}

// 如果e!=nullptr，完成从cache移除*e，并且已经被移除hash table，返回e是否为nullptr
bool LRUCache::FinishErase(LRUHandle *e)
{
    if (e != nullptr)
    {
        assert(e->in_cache_);
        LRU_Remove(e);
        e->in_cache_ = false;
        usage_ -= e->charge_;
        Unref(e);
    }
    // 传入的e!=nullptr都会返回true，一般与table_.Remove()/table_.Insert()搭配使用，
    // 如果table_.Remove()返回的e!=nullptr时，说明e在cache中
    return e != nullptr;
}

void LRUCache::Ref(LRUHandle *e)
{
    if (e->refs_ == 1 && e->in_cache_) // 不在lru_中，移动到in_used_
    {
        LRU_Remove(e);
        LRU_Append(&in_used_, e);
    }
    e->refs_++;
}

void LRUCache::Unref(LRUHandle *e)
{
    assert(e->refs_ > 0);
    --e->refs_;
    if (e->refs_ == 0) // deallocate
    {
        assert(!e->in_cache_);
        e->deleter(e->key(), e->value_);
        free(e);
    }
    else if (e->in_cache_ && e->refs_ == 1) // e不再使用，从in_used_转移到lru_
    {
        LRU_Remove(e);
        LRU_Append(&lru_, e);
    }
}

Cache::Handle *LRUCache::Insert(const Slice &key, uint32_t hash, void *value, size_t charge, void (*deleter)(const Slice &key, void *value))
{
    MutexLock lock(&mutex_);
    LRUHandle *e = reinterpret_cast<LRUHandle *>(malloc(sizeof(LRUHandle) - 1 + key.size()));
    std::memcpy(e->key_data_, key.data(), key.size());
    e->key_length_ = key.size();
    e->value_ = value;
    e->deleter = deleter;
    e->hash_ = hash;
    e->charge_ = charge;
    e->in_cache_ = false;
    e->refs_ = 1; // for return handle
    if (capacity_ > 0)
    {
        ++e->refs_; // for cache handle
        e->in_cache_ = true;
        LRU_Append(&in_used_, e);
        usage_ += charge;
        FinishErase(table_.Insert(e)); // FinishErase掉table_Insert返回旧节点或nullptr,调用FinishErase移除旧节点
    }
    else // 不缓存，容量为0时停止缓存
    {
        //
        e->next_ = nullptr;
    }
    while (usage_ > capacity_ && lru_.next_ != &lru_) // lru_.next_ == &lru_ 时， lru_为空
    {
        LRUHandle *old = &lru_;
        assert(old->refs_ == 1);
        // 移除table_中的(key,hash),如果存在该LRUHandle*,则LRU_Rmove,并UnRef()
        bool erased = FinishErase(table_.Remove(old->key(), old->hash_));
        if (!erased)
        {
            assert(erased);
        }
    }

    return reinterpret_cast<Cache::Handle *>(e);
}

Cache::Handle *LRUCache::Lookup(const Slice &key, uint32_t hash)
{
    MutexLock lock(&mutex_);
    LRUHandle *e = table_.Lookup(key, hash);
    if (e != nullptr)
    {
        Ref(e); // 引用计数加1，并进入in_used_
    }
    return reinterpret_cast<Cache::Handle *>(e);
}

Cache::Cache()
{
}

Cache::~Cache()
{
}

void LRUCache::Release(Cache::Handle *handle)
{
    MutexLock lock(&mutex_);
    Unref(reinterpret_cast<LRUHandle *>(handle));
}

void LRUCache::Erase(const Slice &key, uint32_t hash)
{
    MutexLock lock(&mutex_);
    FinishErase(table_.Remove(key, hash));
}

void LRUCache::Prune()
{
    MutexLock lock(&mutex_);
    while (lru_.next_ != &lru_)
    {
        LRUHandle *e = lru_.next_;
        assert(e->refs_ == 1);
        bool erased = FinishErase(table_.Remove(e->key(), e->hash_));
        if (!erased)
        {
            assert(erased);
        }
    }
}

static const int KNumShardBits = 4;
static const int KNumShards = 1 << KNumShardBits;

class ShardedLRUCache : public Cache
{
private:
    LRUCache shard_[KNumShards];
    port::Mutex id_mutex_;
    uint64_t last_id_;

    static inline std::size_t HashSlice(const Slice &s)
    {
        // TODO: 研究leveldb的hash算法
        return 0;
    }

    static uint32_t Shard(uint32_t hash)
    {
        return hash >> (32 - KNumShardBits);
    }

public:
    explicit ShardedLRUCache(std::size_t capacity) :
        last_id_(0)
    {
        std::size_t per_shard = (capacity + (KNumShards - 1)) / KNumShards; // 计算每个切片的大小
        for (int i = 0; i < KNumShards; ++i)
        {
            shard_[i].SetCapacity(per_shard);
        }
    }

    ~ShardedLRUCache() override
    {
    }

    virtual Handle *Insert(const Slice &key, void *value, size_t charge,
                           void (*deleter)(const Slice &key, void *value)) override;

    virtual Handle *Lookup(const Slice &key) override;

    virtual void Release(Handle *handle) override;

    virtual void *Value(Handle *handle) override;

    virtual void Erase(const Slice &key) override;

    virtual uint64_t NewId() override;

    virtual void Prune() override;

    virtual size_t TotalCharge() const override;
};

void ShardedLRUCache::Prune()
{
    for (int i = 0; i < KNumShards; ++i)
    {
        shard_[i].Prune();
    }
}

size_t ShardedLRUCache::TotalCharge() const
{
    std::size_t usage = 0;
    for (int i = 0; i < KNumShards; ++i)
    {
        usage += shard_[i].TotalCharge();
    }
    return usage;
}
Cache::Handle *ShardedLRUCache::Insert(const Slice &key, void *value, size_t charge, void (*deleter)(const Slice &key, void *value))
{
    uint32_t hash = HashSlice(key);
    Handle *h = shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
    return h;
}

Cache::Handle *ShardedLRUCache::Lookup(const Slice &key)
{
    std::size_t hash = HashSlice(key);
    return shard_[Shard(hash)].Lookup(key, hash);
}

void ShardedLRUCache::Release(Handle *handle)
{
    LRUHandle *h = reinterpret_cast<LRUHandle *>(handle);
    shard_[Shard(h->hash_)].Release(handle);
}

void *ShardedLRUCache::Value(Handle *handle)
{
    return reinterpret_cast<LRUHandle *>(handle)->value_;
}

void ShardedLRUCache::Erase(const Slice &key)
{
    std::size_t hash = HashSlice(key);
    shard_[Shard(hash)].Erase(key, hash);
}

uint64_t ShardedLRUCache::NewId()
{
    MutexLock lock(&id_mutex_);
    return ++(last_id_);
}

Cache *NewLRUCache(size_t capacity)
{
    return new ShardedLRUCache(capacity);
}
} // namespace minidb
